public class Main {

    /**
     * 大数相乘
     */
//    public class Solution {
//        public String solve (String ss, String tt) {
//            //无进位相乘
//            char[] s = new StringBuilder(ss).reverse().toString().toCharArray();
//            char[] t = new StringBuilder(tt).reverse().toString().toCharArray();
//            int n = s.length;
//            int m = t.length;
//            int[] tmp = new int[n + m];
//            for(int i = 0; i < n; i++) {
//                for(int j = 0; j <m; j++) {
//                    tmp[i + j] += (s[i] - '0') * (t[j] - '0');
//                }
//            }
//            //统计结果
//            StringBuffer ret = new StringBuffer();
//            int c = 0;
//            for(int x : tmp) {
//                c += x;
//                ret.append(c % 10);
//                c /= 10;
//            }
//            //细节: c /= 10 后可能已经没有数了在tmp中 此时但是c还有数 那么就需要将剩下的c也拼接上
//            while(c != 0) {
//                ret.append(c % 10);
//                c /= 10;
//            }
//            //处理前岛0 比如 0 * 11111--> 000000 需要将所有0 删除保留最后一个0
//            while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
//                ret.deleteCharAt(ret.length() - 1);
//            }
//            return ret.reverse().toString();
//        }
//    }


    /**
     * 岛屿数量
     */
//    public class Solution {
//        boolean[][] visi;
//        int n;
//        int m;
//        int[] dx = {0, 0, -1, 1};
//        int[] dy = {1, -1, 0, 0};
//        public int solve (char[][] grid) {
//            n = grid.length;
//            m = grid[0].length;
//            visi = new boolean[n][m];
//            int ret = 0;
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < m; j++) {
//                    if (visi[i][j] == false && grid[i][j] == '1') {
//                        visi[i][j] = true;
//                        dfs(grid, i, j);
//                        ret++;
//                    }
//                }
//            }
//            return ret;
//        }
//        //dfs的任务就是将联通块内的所有1 都标记一下 避免重复计算岛屿即可
//        void dfs(char[][] grid, int i, int j) {
//            for (int k = 0; k < 4; k++) {
//                int x = i + dx[k];
//                int y = j + dy[k];
//                if (x >= 0 && x < n && y >= 0 && y < m && visi[x][y] == false &&
//                        grid[x][y] == '1') {
//                    visi[x][y] = true;
//                    dfs(grid, x, y);
//                }
//            }
//        }
//    }

/**
 * 宽度优先遍历2
 */
//    public class Solution {
//        int[] dx = {0, 0, -1, 1};
//        int[] dy = {1, -1, 0, 0};
//        int n;
//        int m;
//        public int solve (char[][] grid) {
//            n = grid.length;
//            m = grid[0].length;
//            int ret = 0;
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < m; j++) {
//                    if (grid[i][j] == '1') {
//                        grid[i][j] = '0';
//                        ret++;
//                        //让bfs帮我去把所有相连的1都改为0
//                        bfs(grid, i, j);
//                    }
//                }
//            }
//            return ret;
//        }
//        public void bfs(char[][] grid, int i, int j) {
//            Queue<int[]> queue = new LinkedList<>();
//            queue.add(new int[] {i, j});
//            while (!queue.isEmpty()) {
//                int[] tmp = queue.poll();
//                for (int k = 0; k < 4; k++) {
//                    int x = tmp[0] + dx[k];
//                    int y = tmp[1] + dy[k];
//                    if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1') {
//                        grid[x][y] = '0';
//                        queue.add(new int[] {x, y});
//                    }
//                }
//            }
//        }
//    }

    /**
     * 求最大公约数的问题
     */
//    public class Main {
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        long x = in.nextLong();
//        for (int i = 0; i < n; i++)  {
//            long tmp = in.nextLong();
//            if (x >= tmp) {
//                x += tmp;
//            } else {
//                x += gcd(x, tmp);
//            }
//        }
//        System.out.println(x);
//    }
//    //求两数的最大公约数
//    static long gcd(long a, long b) {
//        //假设a >= b
//        if (b == 0) return a;
//        return gcd(b, a % b);
//    }

    /**
     * 最大礼物
     */
//    public class Solution {
//        boolean[][] visi;
//        int m;
//        int n;
//        public int maxValue (int[][] grid) {
//            m = grid.length;
//            n = grid[0].length;
//            visi = new boolean[m + 1][n + 1];
//            //注意下标映射
//            int[][] dp = new int[m + 1][n + 1];
//            for (int i = 1; i <= m; i++) {
//                for (int j = 1; j <= n; j++) {
//                    //填表顺序 上->下 左->右
//                    if (visi[i][j] == false) {
//                        visi[i][j] = true;
//                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
//                    }
//                }
//            }
//            return dp[m][n];
//        }
//    }
    /**
     * 对称之类
     * 回文串的题目
     */
//    import java.util.Scanner;
//
//    // 注意类名必须为 Main, 不要有任何 package xxx 信息
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int t = in.nextInt();
//            while (t-- > 0) {
//                int n = in.nextInt();
//                String[] arr = new String[n];
//                for (int i = 0; i < n; i++) {
//                    arr[i] = in.next();
//                }
//                int left = 0;
//                int right = n - 1;
//                while (left < right) {
//                    //判断left 和 right 所指的两字符串是否有相同的字符
//                    if (hasSameChar(arr[left], arr[right])) {
//                        left++;
//                        right--;
//                    } else {
//                        System.out.println("No");
//                        break;
//                    }
//                }
//                if(left >= right) System.out.println("Yes");
//            }
//        }
//        static boolean hasSameChar(String s1, String s2) {
//            boolean[] hash1 = new boolean[26];
//            boolean[] hash2 = new boolean[26];
//            for(char ch : s1.toCharArray()) {
//                hash1[ch - 'a'] = true;
//            }
//            for(char ch : s2.toCharArray()) {
//                hash2[ch - 'a'] = true;
//            }
//            for(int i = 0; i < 26; i++) {
//                if(hash1[i] == hash2[i] && hash1[i] == true) {
//                    return true;
//                }
//            }
//            return false;
//        }
//    }


/**
 * 连续子数组最大和
 */
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            long[] arr = new long[n];
//            for (int i = 0; i < n; i++) {
//                arr[i] = in.nextLong();
//            }
//            long[] dp = new long[n + 1];
//            for (int i = 1; i <= n; i++) {
//                if (dp[i - 1] < 0) {
//                    dp[i] = arr[i - 1];
//
//                } else {
//                    dp[i] = dp[i - 1] + arr[i - 1];
//                }
//            }
//            long ret = - 0x3f3f3f3f;
//            for (int i = 1; i <= n; i++) {
//                ret = Math.max(ret, dp[i]);
//            }
//            System.out.println(ret);
//        }

    /**
     * 经此一役小红所向无敌
     */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            long a = in.nextLong();
//            long h = in.nextLong();
//            long b = in.nextLong();
//            long k = in.nextLong();
//            long ret = 0;
//            //可以提前将将对砍的次数给计算出来
//            long tmp = Math.min(h / b, k / a);
//            ret += tmp * (a + b);
//            h -= b * tmp;
//            k -= a * tmp;
//            if (h > 0 && k > 0) {
//                //进行最后一次对砍
//                h -= b;
//                k -= a;
//                ret += a + b;
//            }
//            if (h > 0 || k > 0) {
//                ret += 10 * (h > 0 ? a : b);
//            }
//            System.out.println(ret);
//        }
//    }


/**
 * 求字符串中最长非回文串
 */
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            char[] strChar = in.next().toCharArray();
//            int len = strChar.length;
//            //先判断是否是回文的 是就len - 1 (特殊情况外) 不是就直接len
//            //判断一个s是否是回文的
//            //特殊情况 就是说全是一样的字符 这样的话一定没有回文串 返回0
//            boolean mark = false;
//            for (int i = 1; i < len; i++) {
//                if (strChar[i - 1] != strChar[i]) {
//                    mark = true;
//                }
//            }
//
//            int left = 0;
//            int right = len - 1;
//            boolean flag = false;
//            while (left < right) {
//                if (strChar[left] == strChar[right]) {
//                    left++;
//                    right--;
//                } else {
//                    flag = true;
//                    break;
//                };
//            }
//            if (flag == false && mark == true) {
//                //正常出while 是回文串
//                System.out.println(len - 1);
//            } else if(flag == true && mark == true){
//                //不是回文串
//                System.out.println(len);
//            } else {
//                System.out.println(0);
//            }
//        }
//    }

}
